#include <iostream>

using namespace std;

int LastRemaining(unsigned int n, unsigned int m)
{
	int *a = new int[n];
	for(int i = 0; i < n; i++)
		a[i] = i;
	
	int left = n, s = 0, k = 0;
	while(left != 1)
	{
		/*每个循环跳每个数*/
		while(true)
		{
			if(a[s] == -1)
			{
				s++;
				s %= n;
				continue;
			}
			if(k < m - 1)
			{
				k++;
				s++;
				s %= n;
			}
			else
				break;
		}
		a[s] = -1;
		k = 0;
		left--;
	}

	int res;
	for(int i = 0; i < n; i++)
		if(a[i] != -1)
			res = a[i];
	
	delete[] a;
	return res;
}

int LastRemaining1(unsigned int n, unsigned int m)
{
	if(n == 1)
		return 0;
	return (LastRemaining1(n - 1, m) + m) % n;
}

int LastRemaining2(unsigned int n, unsigned int m)
{
	int res = 0, k = 0;
	while(k < n - 1)
	{
		res += m;
		res %= k + 2;  //!!!!!!!!!!!!!f(n,m)=[f(n-1,m)+m]%n !!!n=k+2 not n only
		k++;
	}
	
	return res;
}

int LastRemaining_Solution2(int n, unsigned int m)
{
      // invalid input
      if(n <= 0 || m < 0)
            return -1;

      // if there are only one integer in the circle initially,
      // of course the last remaining one is 0
      int lastinteger = 0;

      // find the last remaining one in the circle with n integers
      for (int i = 2; i <= n; i ++) 
            lastinteger = (lastinteger + m) % i;

      return lastinteger;
}

int main()
{
	cout<<LastRemaining(11, 4)<<endl;
	cout<<LastRemaining1(11, 4)<<endl;
	cout<<LastRemaining2(11, 4)<<endl;
	cout<<LastRemaining_Solution2(11, 4)<<endl;
}
